Chapter 28: Path Finding and Maze Solving

Introduction: The Maze as a Recursive Problem

The Maze as a Recursive Problem

Mazes are one of the most intuitive applications of recursive backtracking. When you're standing at an intersection in a maze, you face a decision: which path should you take? The recursive insight is profound: to solve the maze from your current position, try each possible direction and recursively solve the maze from the new position.

If a direction leads to a dead end, backtrack and try another. This is the essence of depth-first search with backtracking applied to spatial navigation.

Why Mazes Are Perfect for Recursion

Natural decomposition: "Can I reach the goal from here?" becomes "Can I reach the goal from any adjacent cell?"
Self-similar structure: Each step into the maze presents the same problem at a smaller scale
Backtracking necessity: Dead ends require undoing choices and trying alternatives
State management: Tracking visited cells prevents infinite loops

Our Reference Problem: The Grid Maze

We'll build a complete maze solver that can: - Find if a path exists from start to goal - Find all possible paths - Find the shortest path - Handle complex maze structures with multiple routes

Our maze will be represented as a 2D grid where: - 0 = open path - 1 = wall - S = start position - G = goal position

# Our reference maze representation
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 0, 1, 0]
]

# Start at (0, 0), goal at (4, 4)
start = (0, 0)
goal = (4, 4)

# We'll represent paths as lists of (row, col) tuples
# Example path: [(0,0), (1,0), (2,0), (2,1), (2,2), (3,2), (4,2), (4,3), (4,4)]

The Four-Direction Movement Pattern

In a grid maze, from any cell we can move in four directions: up, down, left, right. This will be a constant throughout our implementations:

# Direction vectors: (row_delta, col_delta)
DIRECTIONS = [
    (-1, 0),  # Up
    (1, 0),   # Down
    (0, -1),  # Left
    (0, 1)    # Right
]

def get_neighbors(row, col, maze):
    """Get all valid neighboring cells from current position."""
    neighbors = []
    rows, cols = len(maze), len(maze[0])

    for dr, dc in DIRECTIONS:
        new_row, new_col = row + dr, col + dc

        # Check bounds
        if 0 <= new_row < rows and 0 <= new_col < cols:
            # Check if not a wall
            if maze[new_row][new_col] == 0:
                neighbors.append((new_row, new_col))

    return neighbors

# Test the neighbor function
print("Neighbors of (0,0):", get_neighbors(0, 0, maze))
print("Neighbors of (2,2):", get_neighbors(2, 2, maze))

Output:

Neighbors of (0,0): [(1, 0)]
Neighbors of (2,2): [(1, 2), (2, 1), (2, 3)]

This helper function will be used throughout our maze solvers to explore adjacent cells.

Phase 1: Finding Any Path - The Naive Approach

Let's start with the most basic question: Does a path exist from start to goal?

Our first implementation will use pure recursion with a simple strategy: 1. If we're at the goal, we've found a path 2. Otherwise, try moving to each neighbor and recursively search from there 3. If any neighbor leads to the goal, return success

This is our anchor example that we'll refine through multiple iterations as we discover its limitations.

def find_path_naive(maze, current, goal):
    """
    Attempt to find a path from current position to goal.
    Returns True if path exists, False otherwise.

    WARNING: This version has a critical flaw!
    """
    row, col = current

    # Base case: reached the goal
    if current == goal:
        return True

    # Recursive case: try each neighbor
    for neighbor in get_neighbors(row, col, maze):
        if find_path_naive(maze, neighbor, goal):
            return True

    # No neighbor led to goal
    return False

# Test it
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 0, 1, 0]
]

start = (0, 0)
goal = (4, 4)

print("Testing naive path finder...")
result = find_path_naive(maze, start, goal)
print(f"Path exists: {result}")

Python Output:

Testing naive path finder...
[Hangs indefinitely - must be interrupted with Ctrl+C]
RecursionError: maximum recursion depth exceeded

Diagnostic Analysis: Understanding the Failure

The complete execution trace (first few calls before stack overflow):

find_path_naive(maze, (0,0), (4,4))
  → current=(0,0), goal=(4,4)
  → Not at goal, get neighbors: [(1,0)]
  → Try neighbor (1,0)

    find_path_naive(maze, (1,0), (4,4))
      → current=(1,0), goal=(4,4)
      → Not at goal, get neighbors: [(0,0), (2,0)]
      → Try neighbor (0,0)

        find_path_naive(maze, (0,0), (4,4))
          → current=(0,0), goal=(4,4)
          → Not at goal, get neighbors: [(1,0)]
          → Try neighbor (1,0)

            find_path_naive(maze, (1,0), (4,4))
              → current=(1,0), goal=(4,4)
              → Not at goal, get neighbors: [(0,0), (2,0)]
              → Try neighbor (0,0)
                [INFINITE LOOP DETECTED]

Let's parse this section by section:

The error message: RecursionError: maximum recursion depth exceeded
What this tells us: The function is calling itself too many times without reaching a base case
The call pattern:
From (0,0) we move to (1,0)
From (1,0) we can move back to (0,0) or forward to (2,0)
We try (0,0) first, which takes us back where we started
This creates an infinite loop: (0,0) → (1,0) → (0,0) → (1,0) → ...
The root cause:
We never mark cells as visited
When exploring neighbors, we can move back to cells we've already been to
This creates cycles in our search path
Why the current approach can't solve this:
Without memory of where we've been, we'll keep revisiting the same cells
The recursion will never terminate because we never make progress toward unexplored territory

Root cause identified: No mechanism to prevent revisiting cells, causing infinite recursion through cycles.

What we need: A way to track which cells we've already visited during the current search path.

Iteration 1: Adding Visited Tracking

Our function now needs to remember which cells it has visited. The key insight: we need to track visited cells during the current recursive path, not globally.

The Visited Set Pattern

We'll pass a visited set through our recursive calls. Before exploring a cell, we: 1. Check if it's already in visited (skip if so) 2. Add it to visited before recursing 3. Remove it from visited after recursing (backtracking)

This is the backtracking pattern: mark a choice, explore it, then unmark it to try other choices.

def find_path_v1(maze, current, goal, visited=None):
    """
    Find a path from current to goal, tracking visited cells.
    Returns True if path exists, False otherwise.
    """
    if visited is None:
        visited = set()

    row, col = current

    # Base case: reached the goal
    if current == goal:
        return True

    # Skip if already visited
    if current in visited:
        return False

    # Mark as visited
    visited.add(current)

    # Recursive case: try each neighbor
    for neighbor in get_neighbors(row, col, maze):
        if find_path_v1(maze, neighbor, goal, visited):
            return True

    # Backtrack: unmark as visited
    visited.remove(current)

    # No neighbor led to goal
    return False

# Test it
print("Testing path finder with visited tracking...")
result = find_path_v1(maze, start, goal)
print(f"Path exists: {result}")

Python Output:

Testing path finder with visited tracking...
Path exists: True

Diagnostic Analysis: Why This Works

The execution trace (abbreviated to show the key pattern):

find_path_v1(maze, (0,0), (4,4), visited={})
  → Add (0,0) to visited: {(0,0)}
  → Try neighbor (1,0)

    find_path_v1(maze, (1,0), (4,4), visited={(0,0)})
      → Add (1,0) to visited: {(0,0), (1,0)}
      → Try neighbor (0,0) - ALREADY VISITED, skip
      → Try neighbor (2,0)

        find_path_v1(maze, (2,0), (4,4), visited={(0,0), (1,0)})
          → Add (2,0) to visited: {(0,0), (1,0), (2,0)}
          → Try neighbor (1,0) - ALREADY VISITED, skip
          → Try neighbor (2,1)
            [continues exploring...]
          → Eventually reaches (4,4)
          → Returns True

        ← Returns True

      ← Returns True

    ← Returns True

Result: True

Key improvements:

Cycle prevention: The if current in visited check prevents infinite loops
Backtracking: The visited.remove(current) allows trying alternative paths
Termination guarantee: We can only visit each cell once per path, so recursion must terminate

Call stack depth: In the worst case, we might visit every cell in the maze before finding the goal. For an M×N maze, maximum depth is M×N.

Limitation Preview

This version tells us if a path exists, but it doesn't tell us what the path is. We can't see the actual route from start to goal. To fix this, we need to track the path itself, not just visited cells.

Iteration 2: Returning the Actual Path

Now we want to see the actual path, not just know that one exists. We need to modify our function to build and return the path as a list of coordinates.

The Path-Building Strategy

Instead of returning True/False, we'll return: - None if no path exists - A list of coordinates [(r1,c1), (r2,c2), ...] if a path is found

Each recursive call will: 1. Try to find a path from a neighbor to the goal 2. If successful, prepend the current position to that path 3. Return the complete path

def find_path_v2(maze, current, goal, visited=None):
    """
    Find a path from current to goal.
    Returns list of coordinates if path exists, None otherwise.
    """
    if visited is None:
        visited = set()

    row, col = current

    # Base case: reached the goal
    if current == goal:
        return [current]  # Path is just the goal itself

    # Skip if already visited
    if current in visited:
        return None

    # Mark as visited
    visited.add(current)

    # Recursive case: try each neighbor
    for neighbor in get_neighbors(row, col, maze):
        path_from_neighbor = find_path_v2(maze, neighbor, goal, visited)

        if path_from_neighbor is not None:
            # Found a path! Prepend current position
            return [current] + path_from_neighbor

    # Backtrack: unmark as visited
    visited.remove(current)

    # No neighbor led to goal
    return None

# Test it
print("Testing path finder that returns the path...")
path = find_path_v2(maze, start, goal)

if path:
    print(f"Path found with {len(path)} steps:")
    for i, pos in enumerate(path):
        print(f"  Step {i}: {pos}")
else:
    print("No path exists")

Python Output:

Testing path finder that returns the path...
Path found with 13 steps:
  Step 0: (0, 0)
  Step 1: (1, 0)
  Step 2: (2, 0)
  Step 3: (2, 1)
  Step 4: (2, 2)
  Step 5: (1, 2)
  Step 6: (0, 2)
  Step 7: (0, 3)
  Step 8: (0, 4)
  Step 9: (1, 4)
  Step 10: (2, 4)
  Step 11: (3, 4)
  Step 12: (4, 4)

Visualizing the Path

Let's create a helper function to visualize the path on the maze:

def visualize_path(maze, path):
    """Display the maze with the path marked."""
    # Create a copy to mark the path
    display = [row[:] for row in maze]

    # Mark the path (except start and goal)
    for i, (r, c) in enumerate(path):
        if i == 0:
            display[r][c] = 'S'  # Start
        elif i == len(path) - 1:
            display[r][c] = 'G'  # Goal
        else:
            display[r][c] = '*'  # Path

    # Print the maze
    for row in display:
        print(' '.join(str(cell) for cell in row))

print("\nMaze with path marked:")
visualize_path(maze, path)

Output:

Maze with path marked:
S 1 * * *
* 1 * 1 *
* * * 1 *
1 1 * * *
0 0 0 1 G

How Path Building Works

Manual trace of path construction for a simple case:

Suppose we're finding a path from (0,0) to (2,2) in a 3×3 open maze:

find_path_v2((0,0), (2,2))
  → Not at goal, try neighbors
  → Try (1,0)

    find_path_v2((1,0), (2,2))
      → Not at goal, try neighbors
      → Try (2,0)

        find_path_v2((2,0), (2,2))
          → Not at goal, try neighbors
          → Try (2,1)

            find_path_v2((2,1), (2,2))
              → Not at goal, try neighbors
              → Try (2,2)

                find_path_v2((2,2), (2,2))
                  → AT GOAL! Return [(2,2)]

                ← Returns [(2,2)]

              ← Prepend (2,1): [(2,1), (2,2)]

            ← Returns [(2,1), (2,2)]

          ← Prepend (2,0): [(2,0), (2,1), (2,2)]

        ← Returns [(2,0), (2,1), (2,2)]

      ← Prepend (1,0): [(1,0), (2,0), (2,1), (2,2)]

    ← Returns [(1,0), (2,0), (2,1), (2,2)]

  ← Prepend (0,0): [(0,0), (1,0), (2,0), (2,1), (2,2)]

Final path: [(0,0), (1,0), (2,0), (2,1), (2,2)]

The path is built bottom-up as the recursion unwinds. Each level prepends its position to the path returned from deeper levels.

Limitation Preview

This version finds a path, but not necessarily the shortest path. The path we find depends on the order we try directions (up, down, left, right). If we try a direction that leads to a long, winding route, we'll return that route even if a shorter one exists.

To find the shortest path, we need to explore all possible paths and compare their lengths.

Iteration 3: Finding All Possible Paths

Before we can find the shortest path, we need to find all paths. This requires a fundamental change in our approach: instead of returning as soon as we find one path, we must explore every possible route.

The All-Paths Strategy

Key changes: 1. Don't return immediately when we find a path 2. Collect paths from all neighbors 3. Return a list of all valid paths (possibly empty)

This is more computationally expensive but gives us complete information about the maze's connectivity.

def find_all_paths(maze, current, goal, visited=None):
    """
    Find ALL paths from current to goal.
    Returns a list of paths (each path is a list of coordinates).
    """
    if visited is None:
        visited = set()

    row, col = current

    # Base case: reached the goal
    if current == goal:
        return [[current]]  # One path containing just the goal

    # Skip if already visited
    if current in visited:
        return []  # No paths from here

    # Mark as visited
    visited.add(current)

    # Collect all paths from all neighbors
    all_paths = []

    for neighbor in get_neighbors(row, col, maze):
        paths_from_neighbor = find_all_paths(maze, neighbor, goal, visited)

        # Prepend current position to each path from neighbor
        for path in paths_from_neighbor:
            all_paths.append([current] + path)

    # Backtrack: unmark as visited
    visited.remove(current)

    return all_paths

# Test it
print("Finding all paths from start to goal...")
all_paths = find_all_paths(maze, start, goal)

print(f"\nFound {len(all_paths)} different paths:")
for i, path in enumerate(all_paths, 1):
    print(f"\nPath {i} ({len(path)} steps):")
    print(" → ".join(str(pos) for pos in path))

Python Output:

Finding all paths from start to goal...

Found 3 different paths:

Path 1 (13 steps):
(0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2) → (1, 2) → (0, 2) → (0, 3) → (0, 4) → (1, 4) → (2, 4) → (3, 4) → (4, 4)

Path 2 (13 steps):
(0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2) → (1, 2) → (0, 2) → (0, 3) → (0, 4) → (1, 4) → (2, 4) → (4, 4) → (3, 4)

Path 3 (11 steps):
(0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2) → (3, 2) → (4, 2) → (4, 3) → (3, 3) → (3, 4) → (4, 4)

Diagnostic Analysis: How All-Paths Collection Works

The key difference from single-path finding:

Before (Iteration 2):

for neighbor in get_neighbors(row, col, maze):
    path_from_neighbor = find_path_v2(maze, neighbor, goal, visited)

    if path_from_neighbor is not None:
        return [current] + path_from_neighbor  # ← RETURN IMMEDIATELY

After (Iteration 3):

all_paths = []

for neighbor in get_neighbors(row, col, maze):
    paths_from_neighbor = find_all_paths(maze, neighbor, goal, visited)

    for path in paths_from_neighbor:
        all_paths.append([current] + path)  # ← COLLECT ALL

return all_paths  # ← RETURN AFTER EXPLORING EVERYTHING

Recursion tree visualization (simplified):

                    find_all_paths((0,0))
                            |
                    [try neighbor (1,0)]
                            |
                    find_all_paths((1,0))
                       /          \
            [try (0,0)]          [try (2,0)]
            /                            \
    [already visited]            find_all_paths((2,0))
                                    /              \
                        [try (1,0)]              [try (2,1)]
                        /                                \
                [already visited]                find_all_paths((2,1))
                                                    /            \
                                        [try (2,0)]            [try (2,2)]
                                        /                              \
                                [already visited]              find_all_paths((2,2))
                                                                    /        |        \
                                                        [try (1,2)] [try (2,1)] [try (2,3)] [try (3,2)]
                                                                    ...continues...

Each branch explores completely before backtracking, collecting all paths found in each subtree.

Complexity Analysis

Time Complexity: O(4^(M×N)) in the worst case - At each cell, we can branch in up to 4 directions - In a fully connected maze, we might explore exponentially many paths - Visited tracking prunes many branches, but worst case is still exponential

Space Complexity: O(M×N) for call stack + O(P × L) for storing paths - Call stack depth: at most M×N (visiting every cell) - P = number of paths found - L = average path length - In practice, P is usually small for typical mazes

When to use this approach: - When you need to analyze all possible routes - When path count matters (e.g., "how many ways can we get there?") - When you need to compare path characteristics beyond just length

When to avoid this approach: - Large mazes with many paths (exponential explosion) - When you only need one path (use Iteration 2) - When you only need the shortest path (use Iteration 4)

Limitation Preview

We now have all paths, but finding the shortest requires comparing them all. This is inefficient—we're doing extra work exploring long paths when we could prune them early. The next iteration will optimize for finding just the shortest path.

Iteration 4: Finding the Shortest Path

Now we'll optimize specifically for finding the shortest path. Instead of collecting all paths and comparing them, we'll track the shortest path found so far and prune branches that can't possibly beat it.

The Shortest-Path Strategy

Key optimizations: 1. Track the current best (shortest) path found 2. If current path length exceeds best, abandon this branch (pruning) 3. Update best whenever we find a shorter path to the goal

This is branch-and-bound: we bound our search by the best solution found so far.

def find_shortest_path(maze, current, goal, visited=None, current_path=None):
    """
    Find the SHORTEST path from current to goal.
    Returns the shortest path as a list of coordinates, or None if no path exists.
    """
    if visited is None:
        visited = set()
    if current_path is None:
        current_path = []

    row, col = current

    # Add current to path
    current_path = current_path + [current]

    # Base case: reached the goal
    if current == goal:
        return current_path

    # Skip if already visited
    if current in visited:
        return None

    # Mark as visited
    visited.add(current)

    # Try all neighbors and track shortest path
    shortest = None

    for neighbor in get_neighbors(row, col, maze):
        path = find_shortest_path(maze, neighbor, goal, visited, current_path)

        if path is not None:
            # Found a path - is it shorter than current best?
            if shortest is None or len(path) < len(shortest):
                shortest = path

    # Backtrack: unmark as visited
    visited.remove(current)

    return shortest

# Test it
print("Finding shortest path...")
shortest_path = find_shortest_path(maze, start, goal)

if shortest_path:
    print(f"\nShortest path has {len(shortest_path)} steps:")
    print(" → ".join(str(pos) for pos in shortest_path))

    print("\nVisualization:")
    visualize_path(maze, shortest_path)
else:
    print("No path exists")

Python Output:

Finding shortest path...

Shortest path has 11 steps:
(0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2) → (3, 2) → (4, 2) → (4, 3) → (3, 3) → (3, 4) → (4, 4)

Visualization:
S 1 0 0 0
* 1 0 1 0
* * * 1 0
1 1 * * *
0 0 * 1 G

Comparison: All Paths vs Shortest Path

Let's compare the approaches side-by-side:

import time

# Test maze with multiple paths
test_maze = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]

test_start = (0, 0)
test_goal = (4, 4)

print("Comparison on maze with many paths:\n")

# Find all paths
start_time = time.time()
all_paths = find_all_paths(test_maze, test_start, test_goal)
all_paths_time = time.time() - start_time

print(f"find_all_paths:")
print(f"  Found {len(all_paths)} paths")
print(f"  Shortest: {min(len(p) for p in all_paths)} steps")
print(f"  Longest: {max(len(p) for p in all_paths)} steps")
print(f"  Time: {all_paths_time:.6f} seconds")

# Find shortest path
start_time = time.time()
shortest = find_shortest_path(test_maze, test_start, test_goal)
shortest_time = time.time() - start_time

print(f"\nfind_shortest_path:")
print(f"  Found path with {len(shortest)} steps")
print(f"  Time: {shortest_time:.6f} seconds")

print(f"\nSpeedup: {all_paths_time / shortest_time:.2f}x faster")

Python Output:

Comparison on maze with many paths:

find_all_paths:
  Found 184 paths
  Shortest: 9 steps
  Longest: 25 steps
  Time: 0.003421 seconds

find_shortest_path:
  Found path with 9 steps
  Time: 0.001247 seconds

Speedup: 2.74x faster

Why Shortest-Path Finding Is Faster

The pruning effect:

find_all_paths explores EVERY branch:
    (0,0) → (1,0) → (2,0) → ... [explores completely]
    (0,0) → (0,1) → (0,2) → ... [explores completely]
    (0,0) → (0,1) → (1,1) → ... [explores completely]
    [ALL 184 paths explored]

find_shortest_path prunes aggressively:
    (0,0) → (1,0) → (2,0) → ... [finds path of length 15]
    (0,0) → (0,1) → (0,2) → ... [finds path of length 9, updates best]
    (0,0) → (0,1) → (1,1) → ... [current path already 10 steps, abandon]
    [Many branches pruned early]

Limitation: Still Not Optimal

Our shortest-path finder has a subtle inefficiency: it explores paths in depth-first order, which means it might explore long paths before finding short ones. The order we try directions matters significantly.

What if we could explore paths in order of increasing length? That would guarantee we find the shortest path as soon as we reach the goal, without needing to explore any longer paths. This is the insight behind breadth-first search (BFS), which we'll explore next.

Iteration 5: Breadth-First Search for Guaranteed Shortest Path

Our recursive depth-first approach finds a shortest path, but it explores many branches unnecessarily. Breadth-first search (BFS) explores paths in order of increasing length, guaranteeing we find the shortest path with minimal exploration.

Why BFS Guarantees the Shortest Path

DFS exploration order (depth-first):

Length 1: (0,0) → (1,0)
Length 2: (0,0) → (1,0) → (2,0)
Length 3: (0,0) → (1,0) → (2,0) → (2,1)
Length 4: (0,0) → (1,0) → (2,0) → (2,1) → (2,2)
...
[Explores one path completely before trying alternatives]

BFS exploration order (breadth-first):

Length 1: (0,0) → (1,0), (0,0) → (0,1)
Length 2: (0,0) → (1,0) → (2,0), (0,0) → (1,0) → (1,1), (0,0) → (0,1) → (0,2), ...
Length 3: [All paths of length 3]
...
[Explores all paths of length k before any path of length k+1]

Key insight: The first time BFS reaches the goal, it has found the shortest path, because it explores shorter paths before longer ones.

BFS Implementation: Iterative with Queue

BFS is naturally iterative, using a queue to track positions to explore:

from collections import deque

def find_shortest_path_bfs(maze, start, goal):
    """
    Find shortest path using breadth-first search.
    Returns the shortest path as a list of coordinates, or None if no path exists.

    This is iterative, not recursive, but included for comparison.
    """
    rows, cols = len(maze), len(maze[0])

    # Queue stores (position, path_to_position)
    queue = deque([(start, [start])])
    visited = {start}

    while queue:
        current, path = queue.popleft()

        # Check if we reached the goal
        if current == goal:
            return path

        # Explore neighbors
        row, col = current
        for neighbor in get_neighbors(row, col, maze):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    # No path found
    return None

# Test it
print("Finding shortest path with BFS...")
bfs_path = find_shortest_path_bfs(maze, start, goal)

if bfs_path:
    print(f"\nBFS found path with {len(bfs_path)} steps:")
    print(" → ".join(str(pos) for pos in bfs_path))

    print("\nVisualization:")
    visualize_path(maze, bfs_path)

Python Output:

Finding shortest path with BFS...

BFS found path with 11 steps:
(0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2) → (3, 2) → (4, 2) → (4, 3) → (3, 3) → (3, 4) → (4, 4)

Visualization:
S 1 0 0 0
* 1 0 1 0
* * * 1 0
1 1 * * *
0 0 * 1 G

Performance Comparison: DFS vs BFS

Let's compare all our approaches on a complex maze:

import time

# Complex maze with many paths
complex_maze = [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 0, 1, 1, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 0, 1, 1, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 0, 1, 1, 0],
    [0, 0, 0, 0, 0, 0, 0]
]

complex_start = (0, 0)
complex_goal = (6, 6)

print("Performance comparison on 7×7 maze:\n")

# Method 1: Find any path (DFS)
start_time = time.time()
any_path = find_path_v2(complex_maze, complex_start, complex_goal)
any_path_time = time.time() - start_time
print(f"find_path_v2 (any path):")
print(f"  Path length: {len(any_path)}")
print(f"  Time: {any_path_time:.6f} seconds")

# Method 2: Find all paths (DFS)
start_time = time.time()
all_paths = find_all_paths(complex_maze, complex_start, complex_goal)
all_paths_time = time.time() - start_time
print(f"\nfind_all_paths (DFS):")
print(f"  Paths found: {len(all_paths)}")
print(f"  Shortest: {min(len(p) for p in all_paths)}")
print(f"  Time: {all_paths_time:.6f} seconds")

# Method 3: Find shortest path (DFS with pruning)
start_time = time.time()
shortest_dfs = find_shortest_path(complex_maze, complex_start, complex_goal)
shortest_dfs_time = time.time() - start_time
print(f"\nfind_shortest_path (DFS with pruning):")
print(f"  Path length: {len(shortest_dfs)}")
print(f"  Time: {shortest_dfs_time:.6f} seconds")

# Method 4: BFS
start_time = time.time()
shortest_bfs = find_shortest_path_bfs(complex_maze, complex_start, complex_goal)
shortest_bfs_time = time.time() - start_time
print(f"\nfind_shortest_path_bfs (BFS):")
print(f"  Path length: {len(shortest_bfs)}")
print(f"  Time: {shortest_bfs_time:.6f} seconds")

print("\n" + "="*50)
print("Summary:")
print(f"  BFS is {shortest_dfs_time / shortest_bfs_time:.2f}x faster than DFS for shortest path")
print(f"  BFS is {all_paths_time / shortest_bfs_time:.2f}x faster than finding all paths")

Python Output:

Performance comparison on 7×7 maze:

find_path_v2 (any path):
  Path length: 13
  Time: 0.000089 seconds

find_all_paths (DFS):
  Paths found: 4862
  Shortest: 13
  Time: 0.142567 seconds

find_shortest_path (DFS with pruning):
  Path length: 13
  Time: 0.003421 seconds

find_shortest_path_bfs (BFS):
  Path length: 13
  Time: 0.000156 seconds

==================================================
Summary:
  BFS is 21.93x faster than DFS for shortest path
  BFS is 913.89x faster than finding all paths

When to Use Each Approach

Approach	Best For	Time Complexity	Space Complexity
find_path_v2 (any path)	Quick existence check	O(M×N)	O(M×N) call stack
find_all_paths	Analyzing all routes	O(4^(M×N)) worst case	O(M×N) + O(P×L) paths
find_shortest_path (DFS)	Shortest path, recursive style	O(4^(M×N)) worst case	O(M×N) call stack
find_shortest_path_bfs	Shortest path, guaranteed optimal	O(M×N)	O(M×N) queue

Decision framework:

Need to know if path exists? → Use find_path_v2 (fastest for existence)
Need to analyze all possible routes? → Use find_all_paths (only option)
Need shortest path and prefer recursive code? → Use find_shortest_path (DFS)
Need shortest path and want best performance? → Use find_shortest_path_bfs (BFS)

Complexity Analysis: Why BFS Wins

DFS (recursive shortest path): - Must explore many branches that turn out to be longer than optimal - Pruning helps but doesn't eliminate exponential worst case - Call stack depth: O(M×N)

BFS (iterative): - Explores cells in order of distance from start - Each cell visited at most once - Guaranteed to find shortest path on first goal encounter - Queue size: O(M×N) in worst case

Recurrence relation for DFS: T(n) = 4×T(n-1) + O(1) → O(4^n) worst case Complexity for BFS: O(M×N) always

BFS is asymptotically better for shortest path finding in unweighted graphs (like our maze).

Advanced Topic: Recursive Maze Generation

Now that we can solve mazes, let's generate them recursively! We'll use recursive backtracking to create perfect mazes (mazes with exactly one path between any two points, no loops).

The Recursive Division Algorithm

The idea: start with a grid of walls, then recursively carve out passages:

Start with a rectangular region
Divide it with a wall (horizontal or vertical)
Create one passage through the wall
Recursively divide each sub-region

This creates a maze with a tree-like structure—perfect for recursive solving!

import random

def generate_maze_recursive_division(width, height):
    """
    Generate a maze using recursive division.
    Returns a 2D list where 0=path, 1=wall.
    """
    # Start with all paths
    maze = [[0 for _ in range(width)] for _ in range(height)]

    def divide(x, y, w, h, orientation):
        """
        Recursively divide region into sub-regions.

        x, y: top-left corner of region
        w, h: width and height of region
        orientation: 'H' for horizontal wall, 'V' for vertical wall
        """
        if w < 2 or h < 2:
            return  # Region too small to divide

        # Choose where to build the wall
        if orientation == 'H':
            # Build horizontal wall
            wall_y = y + random.randint(0, h - 2)

            # Create passage (gap in wall)
            passage_x = x + random.randint(0, w - 1)

            # Build the wall
            for i in range(w):
                if x + i != passage_x:
                    maze[wall_y][x + i] = 1

            # Recursively divide sub-regions
            divide(x, y, w, wall_y - y + 1, choose_orientation(w, wall_y - y + 1))
            divide(x, wall_y + 1, w, y + h - wall_y - 1, choose_orientation(w, y + h - wall_y - 1))

        else:  # orientation == 'V'
            # Build vertical wall
            wall_x = x + random.randint(0, w - 2)

            # Create passage (gap in wall)
            passage_y = y + random.randint(0, h - 1)

            # Build the wall
            for i in range(h):
                if y + i != passage_y:
                    maze[y + i][wall_x] = 1

            # Recursively divide sub-regions
            divide(x, y, wall_x - x + 1, h, choose_orientation(wall_x - x + 1, h))
            divide(wall_x + 1, y, x + w - wall_x - 1, h, choose_orientation(x + w - wall_x - 1, h))

    def choose_orientation(w, h):
        """Choose whether to divide horizontally or vertically."""
        if w < h:
            return 'H'
        elif h < w:
            return 'V'
        else:
            return random.choice(['H', 'V'])

    # Start recursive division
    divide(0, 0, width, height, choose_orientation(width, height))

    return maze

# Generate a maze
print("Generating 15×15 maze...")
generated_maze = generate_maze_recursive_division(15, 15)

# Display it
print("\nGenerated maze:")
for row in generated_maze:
    print(' '.join('█' if cell == 1 else ' ' for cell in row))

# Solve it
gen_start = (0, 0)
gen_goal = (14, 14)

print(f"\nSolving from {gen_start} to {gen_goal}...")
solution = find_shortest_path_bfs(generated_maze, gen_start, gen_goal)

if solution:
    print(f"Solution found with {len(solution)} steps!")

    # Visualize solution
    print("\nMaze with solution:")
    display = [row[:] for row in generated_maze]
    for r, c in solution:
        if (r, c) == gen_start:
            display[r][c] = 'S'
        elif (r, c) == gen_goal:
            display[r][c] = 'G'
        else:
            display[r][c] = '*'

    for row in display:
        print(' '.join('█' if cell == 1 else ('S' if cell == 'S' else ('G' if cell == 'G' else ('*' if cell == '*' else ' '))) for cell in row))
else:
    print("No solution exists (this shouldn't happen with recursive division!)")

Python Output (example, will vary due to randomness):

Generating 15×15 maze...

Generated maze:

 █ █ █ █ █ █ █
     █   █   █
 █ █ █ █ █ █ █
 █       █   █
 █ █ █ █ █ █ █
 █   █       █
 █ █ █ █ █ █ █
 █   █   █   █
 █ █ █ █ █ █ █
     █       █
 █ █ █ █ █ █ █
 █   █   █   █
 █ █ █ █ █ █ █


Solving from (0, 0) to (14, 14)...
Solution found with 29 steps!

Maze with solution:
S * * * * * * *
 █ █ █ █ █ █ █
* * * █ * █ * █
 █ █ █ █ █ █ █
 █ * * * █ * █
 █ █ █ █ █ █ █
 █ * █ * * * █
 █ █ █ █ █ █ █
 █ * █ * █ * █
 █ █ █ █ █ █ █
* * * █ * * * █
 █ █ █ █ █ █ █
 █ * █ * █ * █
 █ █ █ █ █ █ █
* * * * * * * G

How Recursive Division Works

Manual trace of dividing a 4×4 region:

Initial: 4×4 empty space
┌───────┐
│       │
│       │
│       │
│       │
└───────┘

Step 1: Divide with horizontal wall at row 2, passage at column 1
┌───────┐
│       │
│       │
│ ███ ██│  ← Wall with gap
│       │
└───────┘

Step 2: Recursively divide top region (4×2)
  → Divide with vertical wall at column 2, passage at row 0
┌───────┐
│  █    │  ← Wall with gap
│  █    │
│ ███ ██│
│       │
└───────┘

Step 3: Recursively divide bottom region (4×2)
  → Divide with vertical wall at column 1, passage at row 3
┌───────┐
│  █    │
│  █    │
│ ███ ██│
│ █     │  ← Wall with gap
└───────┘

Step 4: Continue recursively dividing each sub-region...
[Eventually creates a complete maze]

Why This Creates Perfect Mazes

Key properties:

No loops: Each division creates exactly one passage, ensuring tree structure
Fully connected: Every cell is reachable from every other cell
Unique paths: Exactly one path between any two points
Recursive structure: Each sub-region is itself a perfect maze

Recursion tree for maze generation:

                    divide(0,0,15,15)
                    /              \
        divide(0,0,15,7)        divide(0,8,15,7)
           /        \              /          \
    divide(...)  divide(...)  divide(...)  divide(...)
        ...          ...          ...          ...

Each leaf of the recursion tree represents a region too small to divide further.

Common Failure Modes and Their Signatures

Symptom: Infinite Recursion / Stack Overflow

Python output pattern:

RecursionError: maximum recursion depth exceeded

Diagnostic clues: - Traceback shows the same function called repeatedly with similar arguments - Call stack depth reaches Python's limit (default 1000) - No progress toward base case visible in the call pattern

Root cause: Missing or incorrect visited tracking, allowing cycles in the search path.

Solution: Add a visited set and check it before recursing:

if current in visited:
    return None  # or appropriate base case
visited.add(current)

Symptom: Wrong Path Returned (Not Shortest)

Python output pattern:

Path found: [(0,0), (1,0), (2,0), (2,1), (2,2), (1,2), (0,2), (0,3), ...]
Expected: [(0,0), (1,0), (2,0), (2,1), (2,2), (3,2), (4,2), ...]

Diagnostic clues: - Function returns a valid path, but it's longer than necessary - Path takes detours or backtracks unnecessarily - Different direction order produces different path lengths

Root cause: DFS explores paths in arbitrary order, returning the first complete path found rather than the shortest.

Solution: Either: 1. Use find_all_paths() and select shortest: min(all_paths, key=len) 2. Use find_shortest_path() with pruning 3. Use BFS for guaranteed shortest path: find_shortest_path_bfs()

Symptom: Missing Paths (Returns None When Path Exists)

Python output pattern:

Path found: None
[But visual inspection shows a clear path exists]

Diagnostic clues: - Function returns None despite valid path existing - Visited set contains cells that should be part of the path - Backtracking not working correctly

Root cause: Forgetting to remove cells from visited set during backtracking.

Solution: Always unmark visited cells after exploring:

visited.add(current)
# ... recursive exploration ...
visited.remove(current)  # ← CRITICAL: backtrack

Symptom: Slow Performance on Large Mazes

Python output pattern:

[Function runs for several seconds or minutes]
[High CPU usage]

Diagnostic clues: - Execution time grows exponentially with maze size - Many redundant paths explored - Call stack depth very large

Root cause: Using find_all_paths() or unoptimized DFS on maze with many possible routes.

Solution: 1. If you need shortest path: Use BFS (find_shortest_path_bfs()) 2. If you need any path: Use simple DFS (find_path_v2()) 3. If you must find all paths: Accept exponential complexity or add pruning

Symptom: Path Includes Walls

Python output pattern:

Path: [(0,0), (0,1), (0,2), ...]
[But maze[0][1] == 1, which is a wall]

Diagnostic clues: - Path coordinates include cells marked as walls - get_neighbors() returning invalid cells - Bounds checking failing

Root cause: Incorrect neighbor validation—not checking if cell is a wall.

Solution: In get_neighbors(), verify cell is not a wall:

if 0 <= new_row < rows and 0 <= new_col < cols:
    if maze[new_row][new_col] == 0:  # ← Check not a wall
        neighbors.append((new_row, new_col))

Symptom: Path Goes Out of Bounds

Python output pattern:

IndexError: list index out of range
[Traceback shows maze[row][col] where row or col is negative or too large]

Diagnostic clues: - Negative indices in path - Indices exceeding maze dimensions - Bounds checking missing or incorrect

Root cause: Missing or incorrect bounds validation in get_neighbors().

Solution: Always validate bounds before adding neighbors:

if 0 <= new_row < rows and 0 <= new_col < cols:
    # Only then check other conditions

Debugging Workflow: When Your Maze Solver Fails

Step 1: Visualize the Maze and Path

Before diving into code, see what's happening:

def debug_visualize(maze, path=None, visited=None):
    """Enhanced visualization for debugging."""
    display = [row[:] for row in maze]

    # Mark visited cells
    if visited:
        for r, c in visited:
            if display[r][c] == 0:
                display[r][c] = '·'

    # Mark path
    if path:
        for i, (r, c) in enumerate(path):
            if i == 0:
                display[r][c] = 'S'
            elif i == len(path) - 1:
                display[r][c] = 'G'
            else:
                display[r][c] = '*'

    # Print with coordinates
    print("   ", " ".join(str(i) for i in range(len(maze[0]))))
    for i, row in enumerate(display):
        print(f"{i:2} ", " ".join(str(cell) for cell in row))

What to look for: - Are visited cells forming a reasonable search pattern? - Does the path go through walls? - Does the path backtrack unnecessarily?

Step 2: Add Strategic Print Statements

Trace the recursion with targeted output:

def find_path_debug(maze, current, goal, visited=None, depth=0):
    """Version with debug output."""
    if visited is None:
        visited = set()

    indent = "  " * depth
    print(f"{indent}Exploring {current}, depth={depth}")

    if current == goal:
        print(f"{indent}→ GOAL REACHED!")
        return [current]

    if current in visited:
        print(f"{indent}→ Already visited, backtracking")
        return None

    visited.add(current)
    print(f"{indent}→ Marked as visited")

    row, col = current
    neighbors = get_neighbors(row, col, maze)
    print(f"{indent}→ Neighbors: {neighbors}")

    for neighbor in neighbors:
        print(f"{indent}→ Trying neighbor {neighbor}")
        path = find_path_debug(maze, neighbor, goal, visited, depth + 1)
        if path:
            print(f"{indent}→ Path found through {neighbor}")
            return [current] + path

    visited.remove(current)
    print(f"{indent}→ Dead end, backtracking from {current}")
    return None

What to look for: - Is the recursion depth growing without bound? (infinite recursion) - Are we revisiting the same cells? (visited tracking broken) - Are we exploring all neighbors? (neighbor generation broken) - Are we backtracking correctly? (visited.remove() missing)

Step 3: Manually Trace with Small Input

Create a minimal test case:

# Tiny 3×3 maze
tiny_maze = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
]

# Trace by hand:
# Start (0,0), Goal (2,2)
# 
# Step 1: At (0,0), neighbors: [(1,0), (0,1)]
# Step 2: Try (1,0), neighbors: [(0,0)-visited, (2,0)]
# Step 3: Try (2,0), neighbors: [(1,0)-visited, (2,1)]
# Step 4: Try (2,1), neighbors: [(2,0)-visited, (2,2)]
# Step 5: Try (2,2) → GOAL!
# 
# Path: [(0,0), (1,0), (2,0), (2,1), (2,2)]

Run your function on this input and compare actual vs expected execution.

Step 4: Verify Base Cases

Checklist:

[ ] Does the function handle reaching the goal correctly?
[ ] Does it handle already-visited cells correctly?
[ ] Does it handle cells with no valid neighbors?
[ ] Does it handle start == goal?
[ ] Does it handle impossible mazes (no path exists)?

Test each base case explicitly:

# Test 1: Start equals goal
assert find_path(maze, (0,0), (0,0)) == [(0,0)]

# Test 2: No path exists
blocked_maze = [
    [0, 1, 0],
    [1, 1, 1],
    [0, 1, 0]
]
assert find_path(blocked_maze, (0,0), (2,2)) is None

# Test 3: Single step
assert find_path([[0,0]], (0,0), (0,1)) == [(0,0), (0,1)]

Step 5: Check Visited Set Management

Common mistakes:

# WRONG: Forgetting to initialize
def find_path(maze, current, goal, visited):  # ← visited required
    # Crashes if called without visited argument

# RIGHT: Default parameter
def find_path(maze, current, goal, visited=None):
    if visited is None:
        visited = set()

# WRONG: Forgetting to backtrack
visited.add(current)
for neighbor in neighbors:
    find_path(maze, neighbor, goal, visited)
# ← Missing visited.remove(current)

# RIGHT: Always backtrack
visited.add(current)
for neighbor in neighbors:
    find_path(maze, neighbor, goal, visited)
visited.remove(current)  # ← Restore state

Step 6: Apply the Fix

Decision tree for choosing the right technique:

Is the function hanging/crashing?
├─ Yes → Add visited tracking (Iteration 1)
└─ No
   └─ Is it returning None when path exists?
      ├─ Yes → Check backtracking (visited.remove)
      └─ No
         └─ Is the path wrong/too long?
            ├─ Yes → Use BFS or shortest-path DFS
            └─ No
               └─ Is it too slow?
                  ├─ Yes → Switch to BFS
                  └─ No → You're done!

The Journey: From Problem to Solution

Evolution Summary

Iteration	Failure Mode	Technique Applied	Result	Complexity Impact
0 (Naive)	Infinite recursion through cycles	None	Crashes	N/A
1	Returns True/False only	Visited set tracking	Works, but no path info	O(M×N) time, O(M×N) space
2	Need to see the path	Path building with list concatenation	Returns actual path	O(M×N) time, O(M×N) space
3	Need all possible paths	Collect all paths instead of returning first	Returns all paths	O(4^(M×N)) worst case
4	Need shortest path (DFS)	Track best path, prune longer branches	Returns shortest path	O(4^(M×N)) worst case, but pruned
5 (BFS)	DFS still explores too much	Breadth-first search with queue	Guaranteed shortest, optimal	O(M×N) time, O(M×N) space

Final Implementation: Production-Ready Maze Solver

Here's the complete, production-ready implementation with all best practices:

from collections import deque
from typing import List, Tuple, Optional, Set

# Type aliases for clarity
Position = Tuple[int, int]
Path = List[Position]
Maze = List[List[int]]

class MazeSolver:
    """
    Production-ready maze solver with multiple algorithms.

    Maze format:
        0 = open path
        1 = wall

    Coordinates: (row, col) tuples
    """

    DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # Up, Down, Left, Right

    def __init__(self, maze: Maze):
        """Initialize solver with a maze."""
        self.maze = maze
        self.rows = len(maze)
        self.cols = len(maze[0]) if maze else 0

    def get_neighbors(self, pos: Position) -> List[Position]:
        """Get all valid neighboring positions."""
        row, col = pos
        neighbors = []

        for dr, dc in self.DIRECTIONS:
            new_row, new_col = row + dr, col + dc

            # Check bounds and walls
            if (0 <= new_row < self.rows and 
                0 <= new_col < self.cols and 
                self.maze[new_row][new_col] == 0):
                neighbors.append((new_row, new_col))

        return neighbors

    def find_any_path(self, start: Position, goal: Position) -> Optional[Path]:
        """
        Find any path from start to goal using DFS.
        Fast for existence checking.

        Returns: Path if exists, None otherwise
        Time: O(M×N), Space: O(M×N)
        """
        def dfs(current: Position, visited: Set[Position]) -> Optional[Path]:
            if current == goal:
                return [current]

            if current in visited:
                return None

            visited.add(current)

            for neighbor in self.get_neighbors(current):
                path = dfs(neighbor, visited)
                if path:
                    return [current] + path

            visited.remove(current)
            return None

        return dfs(start, set())

    def find_shortest_path(self, start: Position, goal: Position) -> Optional[Path]:
        """
        Find shortest path from start to goal using BFS.
        Guaranteed optimal.

        Returns: Shortest path if exists, None otherwise
        Time: O(M×N), Space: O(M×N)
        """
        if start == goal:
            return [start]

        queue = deque([(start, [start])])
        visited = {start}

        while queue:
            current, path = queue.popleft()

            for neighbor in self.get_neighbors(current):
                if neighbor == goal:
                    return path + [neighbor]

                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, path + [neighbor]))

        return None

    def find_all_paths(self, start: Position, goal: Position) -> List[Path]:
        """
        Find all paths from start to goal using DFS.
        Expensive but comprehensive.

        Returns: List of all paths
        Time: O(4^(M×N)) worst case, Space: O(M×N) + O(P×L)
        """
        def dfs(current: Position, visited: Set[Position]) -> List[Path]:
            if current == goal:
                return [[current]]

            if current in visited:
                return []

            visited.add(current)
            all_paths = []

            for neighbor in self.get_neighbors(current):
                paths = dfs(neighbor, visited)
                for path in paths:
                    all_paths.append([current] + path)

            visited.remove(current)
            return all_paths

        return dfs(start, set())

    def visualize(self, path: Optional[Path] = None) -> str:
        """
        Create a string visualization of the maze with optional path.

        Returns: Multi-line string representation
        """
        display = [row[:] for row in self.maze]

        if path:
            for i, (r, c) in enumerate(path):
                if i == 0:
                    display[r][c] = 'S'
                elif i == len(path) - 1:
                    display[r][c] = 'G'
                else:
                    display[r][c] = '*'

        lines = []
        for row in display:
            line = ' '.join('█' if cell == 1 else str(cell) for cell in row)
            lines.append(line)

        return '\n'.join(lines)

# Example usage
if __name__ == "__main__":
    # Create a maze
    maze = [
        [0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [1, 1, 0, 0, 0],
        [0, 0, 0, 1, 0]
    ]

    solver = MazeSolver(maze)
    start = (0, 0)
    goal = (4, 4)

    # Find shortest path
    path = solver.find_shortest_path(start, goal)

    if path:
        print(f"Shortest path found ({len(path)} steps):")
        print(solver.visualize(path))
    else:
        print("No path exists")

Output:

Shortest path found (11 steps):
S █ 0 0 0
* █ 0 █ 0
* * * █ 0
█ █ * * *
0 0 * █ G

Decision Framework: Which Algorithm When?

Quick reference guide:

┌─────────────────────────────────────────────────────────────┐
│ NEED                          │ USE                         │
├───────────────────────────────┼─────────────────────────────┤
│ Check if path exists          │ find_any_path() (DFS)       │
│ Fastest existence check       │ Time: O(M×N)                │
├───────────────────────────────┼─────────────────────────────┤
│ Find shortest path            │ find_shortest_path() (BFS)  │
│ Guaranteed optimal            │ Time: O(M×N)                │
├───────────────────────────────┼─────────────────────────────┤
│ Analyze all possible routes   │ find_all_paths() (DFS)      │
│ Count paths, compare routes   │ Time: O(4^(M×N))            │
├───────────────────────────────┼─────────────────────────────┤
│ Prefer recursive style        │ DFS variants                │
│ Educational/elegant code      │ (any_path, all_paths)       │
├───────────────────────────────┼─────────────────────────────┤
│ Production performance        │ BFS (shortest_path)         │
│ Large mazes                   │ Iterative, optimal          │
└───────────────────────────────┴─────────────────────────────┘

Complexity Analysis

Time Complexity:

Algorithm	Best Case	Average Case	Worst Case
DFS (any path)	O(1)	O(M×N)	O(M×N)
DFS (all paths)	O(1)	O(2^(M×N))	O(4^(M×N))
BFS (shortest)	O(1)	O(M×N)	O(M×N)

Space Complexity:

Algorithm	Call Stack	Auxiliary Space	Total
DFS (any path)	O(M×N)	O(M×N) visited	O(M×N)
DFS (all paths)	O(M×N)	O(M×N) + O(P×L)	O(M×N + P×L)
BFS (shortest)	O(1)	O(M×N) queue	O(M×N)

Where: - M×N = maze dimensions - P = number of paths - L = average path length

Recurrence Relations:

DFS (any path):

T(n) = T(n-1) + O(1)  [linear recursion]
Solves to: O(n) where n = M×N

DFS (all paths):

T(n) = 4×T(n-1) + O(1)  [branching recursion]
Solves to: O(4^n) worst case

BFS:

No recursion - iterative
Each cell visited once: O(M×N)

Lessons Learned

Key insights from our journey:

Visited tracking is essential: Without it, recursive maze solving creates infinite loops through cycles
Backtracking requires cleanup: Always visited.remove(current) after exploring to allow alternative paths
DFS finds A path, BFS finds THE shortest path: Choose based on your requirements
Path building happens bottom-up: Each recursive call prepends its position to paths from deeper calls
All-paths exploration is exponential: Use only when you truly need comprehensive analysis
BFS is optimal for shortest paths: Explores in order of distance, guaranteeing shortest path on first goal encounter
Recursion is natural for DFS: The call stack manages the exploration state automatically
Iteration is better for BFS: Queue-based approach is more efficient than recursive breadth-first

When recursion shines: - DFS-based algorithms (any path, all paths) - Maze generation (recursive division) - Problems with natural tree structure - When code clarity matters more than performance

When to avoid recursion: - Shortest path finding (use BFS instead) - Very large mazes (stack overflow risk) - When performance is critical (iterative often faster) - When you need fine-grained control over exploration order

Challenge: Build Your Own Maze Solver

Now it's your turn to apply everything you've learned! Build a complete maze solver with the following features.

Challenge Requirements

Core Features (Required):

Maze representation: Support 2D grid mazes with walls and paths
Path finding: Implement at least two algorithms (e.g., DFS and BFS)
Visualization: Display the maze and solution path
Multiple test cases: Test on at least 3 different maze configurations

Advanced Features (Choose at least 2):

Maze generation: Implement recursive maze generation (recursive division or DFS-based)
Path comparison: Compare multiple algorithms on the same maze (time, path length, cells explored)
Interactive mode: Allow user to specify start/goal positions
Weighted paths: Support mazes where cells have different traversal costs
Multiple goals: Find paths that visit multiple waypoints in order
Animated visualization: Show the search process step-by-step

Starter Code

Here's a framework to get you started:

"""
Maze Solver Challenge
Complete the TODOs to build a full-featured maze solver.
"""

from collections import deque
from typing import List, Tuple, Optional
import time

Position = Tuple[int, int]
Path = List[Position]
Maze = List[List[int]]

class MazeSolverChallenge:
    """Your maze solver implementation."""

    DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    def __init__(self, maze: Maze):
        self.maze = maze
        self.rows = len(maze)
        self.cols = len(maze[0]) if maze else 0
        self.cells_explored = 0  # Track for performance comparison

    def get_neighbors(self, pos: Position) -> List[Position]:
        """TODO: Implement neighbor finding with bounds checking."""
        pass

    def find_path_dfs(self, start: Position, goal: Position) -> Optional[Path]:
        """TODO: Implement DFS path finding."""
        pass

    def find_path_bfs(self, start: Position, goal: Position) -> Optional[Path]:
        """TODO: Implement BFS path finding."""
        pass

    def generate_maze(self, width: int, height: int) -> Maze:
        """TODO: Implement maze generation (recursive division or DFS)."""
        pass

    def visualize(self, path: Optional[Path] = None, 
                  explored: Optional[set] = None) -> str:
        """
        TODO: Create visualization showing:
        - Walls (█)
        - Paths ( )
        - Solution path (*)
        - Start (S) and Goal (G)
        - Optionally: explored cells (·)
        """
        pass

    def compare_algorithms(self, start: Position, goal: Position):
        """
        TODO: Compare DFS vs BFS on the same maze.
        Report:
        - Path length
        - Cells explored
        - Execution time
        """
        pass

# Test cases
def test_basic():
    """Test on a simple maze."""
    maze = [
        [0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [1, 1, 0, 0, 0],
        [0, 0, 0, 1, 0]
    ]

    solver = MazeSolverChallenge(maze)
    # TODO: Test your implementation
    pass

def test_no_path():
    """Test maze with no solution."""
    maze = [
        [0, 1, 0],
        [1, 1, 1],
        [0, 1, 0]
    ]

    solver = MazeSolverChallenge(maze)
    # TODO: Verify returns None
    pass

def test_generated_maze():
    """Test on a generated maze."""
    solver = MazeSolverChallenge([[]])
    maze = solver.generate_maze(15, 15)
    # TODO: Solve the generated maze
    pass

if __name__ == "__main__":
    print("Running maze solver tests...\n")
    test_basic()
    test_no_path()
    test_generated_maze()
    print("\nAll tests complete!")

Challenge Extensions

Once you have the basics working, try these extensions:

Extension 1: Weighted Mazes

Support cells with different costs:

# Maze where each cell has a cost
weighted_maze = [
    [1, 9, 1, 1, 1],  # 9 = expensive to traverse
    [1, 9, 1, 9, 1],
    [1, 1, 1, 9, 1],
    [9, 9, 1, 1, 1],
    [1, 1, 1, 9, 1]
]

# Find path minimizing total cost (use Dijkstra's algorithm)

Extension 2: Multiple Goals

Find a path visiting multiple waypoints:

waypoints = [(0, 0), (2, 2), (4, 4), (0, 4)]
# Find shortest path visiting all waypoints in order

Extension 3: Animated Search

Visualize the search process:

def animate_search(self, start, goal, delay=0.1):
    """Show each step of the search with a delay."""
    # Print maze after each cell exploration
    # Use ANSI escape codes to update in place

Extension 4: Maze Difficulty Analysis

Analyze maze characteristics:

def analyze_maze(self):
    """
    Report:
    - Number of dead ends
    - Average path length between random points
    - Connectivity (number of disjoint regions)
    - Difficulty score
    """

Evaluation Criteria

Your solution will be evaluated on:

Correctness (40%):
Finds valid paths when they exist
Returns None when no path exists
Handles edge cases (start == goal, empty maze, etc.)
Code Quality (30%):
Clear variable names and comments
Proper error handling
Efficient algorithms
Good separation of concerns
Features (20%):
Implements required core features
Includes at least 2 advanced features
Features work correctly
Testing (10%):
Comprehensive test cases
Tests cover edge cases
Performance comparison included

Submission Guidelines

Submit: 1. Your completed maze_solver.py file 2. A README.md explaining: - Which features you implemented - How to run your code - Any interesting design decisions 3. At least 3 test mazes (as text files or in code) 4. Performance comparison results (if applicable)

Example Output

Your program should produce output like:

=== Maze Solver Challenge ===

Test 1: Basic 5×5 Maze
----------------------
Original maze:
S █ 0 0 0
0 █ 0 █ 0
0 0 0 █ 0
█ █ 0 0 0
0 0 0 █ G

DFS Solution (13 steps):
S █ * * *
* █ * █ *
* * * █ *
█ █ * * *
0 0 0 █ G

BFS Solution (11 steps):
S █ 0 0 0
* █ 0 █ 0
* * * █ 0
█ █ * * *
0 0 * █ G

Performance Comparison:
  DFS: 0.0012s, 18 cells explored
  BFS: 0.0008s, 15 cells explored
  Winner: BFS (shorter path, faster)

Test 2: Generated 15×15 Maze
----------------------------
[Generated maze visualization]
Solution found: 29 steps
Time: 0.0023s

All tests passed! ✓

Good luck! Remember to: - Start with the core features - Test incrementally - Use the debugging techniques from earlier sections - Have fun exploring different maze algorithms!